<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <title>Title</title>
</head>
<body>

</body>
<script>
  // 合并排序就是先拆分，分为左边右边，一直分到只有一个元素，然后在左右对比做合并
  /**
   * 合并两个已排序的数组
   * @param {Array} left - 第一个已排序数组
   * @param {Array} right - 第二个已排序数组
   * @returns {Array} 合并后的新排序数组
   */
  function merge(left, right) {
    // 存储合并结果的临时数组
    let temp = []
    let i = 0  // left数组的索引
    let j = 0  // right数组的索引

    // 比较两个数组的元素并按顺序合并
    while (i < left.length && j < right.length) {
      if (left[i] < right[j]) {
        temp.push(left[i])
        i++
      } else {
        temp.push(right[j])
        j++
      }
    }

    // 将剩余元素拼接到结果数组
    return [...temp, ...left.slice(i), ...right.slice(j)]
  }

  /**
   * 归并排序算法实现
   * @param {Array} arr - 待排序数组
   * @returns {Array} 排序后的新数组
   */
  function mergeSort(arr) {
    // 递归终止条件：数组长度小于等于1时直接返回
    if (arr.length <= 1) return arr

    // 分割数组为左右两部分
    const mid = Math.floor(arr.length / 2)
    const left = arr.slice(0, mid)
    const right = arr.slice(mid)

    // 递归排序并合并子数组
    return merge(mergeSort(left), mergeSort(right))
  }

  const arr = [5, 3, 8, 4, 2, 7, 1, 6];
  console.log(mergeSort(arr))
</script>
</html>